package pers.sloera.leetcode.editor.cn;

/**
 * 石子游戏 II
 *
 * @author sloera
 * @date 2023-02-22 22:01:34
 */
class StoneGameIi {
    public static void main(String[] args) {
        Solution solution = new StoneGameIi().new Solution();
        System.out.println(solution.stoneGameII(new int[]{2, 7, 9, 4, 4}));
        System.out.println(solution.stoneGameII(new int[]{1, 2, 3, 4, 5, 100}));
        System.out.println(solution.stoneGameII(new int[]{1}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int stoneGameII(int[] piles) {
            if (piles.length <= 0) {
                return 0;
            }
            // 前缀和，方便计算拿起的石子
            int[] sumPrefix = new int[piles.length + 1];
            for (int i = 0; i < piles.length; i++) {
                sumPrefix[i + 1] = sumPrefix[i] + piles[i];
            }
            // dp[i][j] 从[i: length-1]，m为j时的最大值
            // 对于dp，得先知道后面的最大值，才能得到当前的最大值，因此逆序
            int[][] dp = new int[piles.length][piles.length + 1];
            // 至少可以拿走一个
            dp[0][1] = piles[0];
            for (int i = piles.length - 1; i >= 0; i--) {
                // 对于每堆，遍历所有的m得到对应的最值
                for (int m = 1; m < piles.length; m++) {
                    int leftTotal = sumPrefix[piles.length] - sumPrefix[i];
                    if (i + 2 * m >= piles.length) { // 能拿完就拿完
                        dp[i][m] = leftTotal;
                    } else {
                        // 遍历x的取值范围1到2m内
                        for (int x = 1; x <= 2 * m; x++) {
                            // 两个都不是傻子，只有我是傻子，所以要遍历i+x最大时，哪个x我能拿到最多（剩余堆减去另一个人能取得的最大值）
                            dp[i][m] = Math.max(dp[i][m], leftTotal - dp[i + x][Math.max(m, x)]);
                        }
                    }
                }
            }
            // 从0开始，m为1时的最大值
            return dp[0][1];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
